public class QuickSort {
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void quickSort(int[] arr, int left, int right) {
        quick(arr,0,arr.length-1);
    }
    private static void quick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = partition(arr,left,right);
        quick(arr,left,pivot-1);
        quick(arr,pivot+1,right);
    }
    private static int partition(int[] arr, int left, int right) {
        int temp=arr[left];
        while(left<right) {
            while(left<right && arr[right]>=temp) {
                right--;
            }
            arr[left]=arr[right];
            while(left<right && arr[left]<=temp) {
                left++;
            }
            arr[right]=arr[left];
        }
        arr[left]=temp;
        return left;
    }

}
